1. Field of the Invention
The present invention generally relates to data communications, such as local area networks (LAN) and, more particularly, to a method and apparatus for controlling the transmission across a data link.
2. Description of the Related Art
In general, there are a variety of basic mechanisms for transmitting information between two or more information source/sink devices (referred to in the art as data terminal equipment or DTE) on a particular data link. However, in order to ensure the reliable exchange (i.e. to a high probability free of errors and duplications) of meaningful messages between any two DTEs in a data link, it is necessary to define a set of rules, or control procedures, which must be adopted by all the communicating nodes. These rules or procedures are commonly known as communication protocols.
In order to insure compatible development throughout the industry, standards have been set for basic DTE operational specifications, e.g. IEEE 802.3, Carrier Sense, Multiple Access with Collision Detection (CSMA/CD) for LANs. This is the basic data packet standard (where a "packet" is a self-contained message unit comprising information less than the entire message being sent). This standard is used to control access to a shared transmission medium such as a coaxial cable bus to which a number of DTE stations are connected.
The physical transfer is accomplished by data buffering, where anywhere from approximately 128 to 4096 bytes may be buffered (the physical media may limit the maximum, e.g. Ethernet/IEEE 802.3 is limited to 1514 bytes per transferred data field).
In designing communication equipment, there are trade-offs. Larger buffers increase efficiency but smaller buffers require less memory hardware. In practice, smaller buffers may have higher throughput even if the error rate is high, since less data has to be retransmitted to recover from a bad packet.
There are different types of packets. Some contain control information; others contain user data.
Packets, in turn, have different parts. Delimiters mark the start and end of a packet, framing the packet. They are also used to synchronize the transmitter and receiver sections of the DTEs on the link. Frame structure is concerned with defining each unit of information transferred across a data link. Typically there are control frames (C-FRAMES) for link management and information frames (I-FRAMES) for the transfer of user's message data. Typical information frames and control frames are shown in FIGS. 5a and 5b, respectively. The header at the beginning of a packet identifies the type of packet information, viz, control or data. Data packets contain the user's data (as opposed to data which the protocol understands). Control packets relate to information established by the protocol.
Protocols are generally organized into layers, each layer operating more or less independently. For example, in the open systems interconnection (OSI) model of the International Standards Organization, a seven layer standard, shown in FIG. 1, has been adopted to make multi-vendor networking products easier to accomplish. The types of frames and messages used by each layer vary since they each perform different and complementary functions. For example, higher level software layers communicate over the link by exchanging messages using the resources provided by lower layers. Link Layer protocol is concerned with providing reliable transmission on the data link, viz., providing a reliable transport facility across the physical transmission media link between DTEs. Important components of a Link Level protocol are connection management, error control and flow control.
Error control is concerned with both error detection and correction. The quantum of recovery is a packet. Error detection is usually determined by using a Cyclic Redundancy Check (CRC in FIGS. 5a and 5b), a numeric value computed from the data in the message transmitted which is compared to the value generated from the data received. Error recovery is achieved by rejection of the bad packet by the receiving DTE node on the link and retransmission from the transmitting DTE node on the link.
Flow control is concerned with controlling the rate of transmission of elements--characters or frames of characters--on a link. Transmission and reception are generally asynchronous processes. Therefore, flow control is necessary so that the receiver always has sufficient buffer storage resources to accept each element sent to it, i.e. to prevent the transmitter from overrunning the receiver. The common means for achieving flow control is by using "start" and "stop" control messages.
In general, a Link Layer protocol can be considered as being concerned with several intricacies of communicating over a link: first, with the intial setting up of the link to ensure both parties are ready to exchange information, second, with the ordered exchange of data blocks or messages across the link, and third, with the orderly release or clearing of the link. The present invention relates to the first and second. A number of control messages are needed to perform the various functions.
One common type of Link Layer protocol for bidirectional transmission on a link is commonly known as the sliding window protocol. The essence of all sliding window protocols is that at any instant of time, the transmitting node maintains a list of consecutive sequence numbers corresponding to frames it is permitted to send. These frames are said to fall within the sending window. Similarly, the receiving node also maintains a receiving window corresponding to frames it is permitted to accept. The protocol is required to deliver the messages to the destination DTE in the same order they were passed from the source DTE. Since frames currently within the sender's window may ultimately be lost or damaged in transit, the sender must keep all these frames in its memory for possible retransmission. Thus, the sequence numbers of the transmitted frames within the sender's window represent frames sent but not acknowledged. Whenever a new message arrives from the host DTE, it is given the next highest sequence number, and the upper edge of the sender's window is advanced by one. When an acknowledgement comes in, the lower edge is advanced by one. In this way the sender's window continuously maintains a list of unacknowledged frames. The receiver's window corresponds to the frames it may accept. When a frame whose sequence number is equal to the lower edge of the window is received, it is passed to the host receiving DTE, an acknowledgement is generated, and the window is rotated by one. For additional detail on sliding window protocol, reference to a text such as COMPUTER NETWORKS, A. S. Tanenbaum, copyright 1981, Prentice-Hall, Inc., Chap. 4.2, is recommended.
Known data link protocols assume that a data packet of a particular sequence number is available for re-use (i.e. receiver buffer space is available) when the data have been acknowledged. However, when data rates are high compared to the total amount of buffer space, this often is not the case, causing "stop" and "start" packets to be sent excessively. At very high speeds, a "stop" packet may not arrive in time. Therefore, one or more packets will be lost at the receiving DTE for lack of buffer space. An error recovery mechanism would then have to be used to recover the data. This wastes time and link bandwidth.
In prior art protocols, large numbers of buffers are often required, prohibiting one-chip integrated circuit solutions. Packet headers are very complex, using encoded fields to transmit each individual control instruction. Thus, decoding is complex, requiring complex hardware.
Other problems also occur due to the nature of the physical transmission media, e.g., two-wire open lines, twisted pair lines, coaxial cables, and optical fibers.
Hence, there is a need to improve the reliability of the data packets in data links. Additionally, there is a need to provide a communication protocol which works effectively at high speed transmission rates.